package likou.tanxin;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/10 07:14
 */
public class _31 {
    public static void main(String[] args) {
        nextPermutation(new int[]{1, 3, 2});
    }

    public static void nextPermutation(int[] nums) {
        boolean p = true;//如果无序，则为false
        //两个顺序的位置交换
        int[] swaps = new int[nums.length];
        Arrays.fill(swaps, -1);
        for (int i = nums.length - 1; i >= 0; i--) {
            for (int j = i - 1; j >= 0; j--) {
                if (nums[i] > nums[j]) {
                    swaps[i] = j;
                    //有一个顺序，就为false
                    p = false;
                    break;
                }
            }
        }
        if (p) {
            Arrays.sort(nums);
            return;
        }
        int left = 0;
        int right = 0;
        for (int i = 0; i < swaps.length; i++) {
            if (swaps[i] != -1 && swaps[i] >= left) {
                left = swaps[i];
                right = i;
            }
        }
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
        Arrays.sort(nums,right,nums.length);
    }


    class Solution {
        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while (i >= 0 && nums[i + 1] <= nums[i]) {
                i--;
            }
            if (i >= 0) {
                int j = nums.length - 1;
                while (j >= 0 && nums[j] <= nums[i]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1);
        }

        public void reverse(int[] nums, int start) {
            int i = start;
            int j = nums.length - 1;
            while (i < j) {
                swap(nums, i, j);
                i++;
                j--;
            }
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }
    }
}
